package leetcode;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-12-23 21:46
 **/
public class LeetCode96 {

    //动态规划
    /*public int numTrees(int n) {
        //g[i]: 表示表示长度为n的序列能构成的不同二叉搜索树的个数
        int[] g = new int[n + 1];
        //g[0]:空树,g[1]只有一个序列构成二叉搜索树的个数
        g[0] = 1;
        g[1] = 1;

        for (int i = 2; i <= n; ++i) {
            //计算f(j, i) = G[j - 1] * G[i - j);
            for (int j = 1; j <= i; ++j) {
                g[i] += g[j - 1] * g[i - j];
            }
        }

        return g[n];
    }*/

    //数学
    public int numTrees(int n) {
        // 提示：我们在这里需要用 long 类型防止计算过程中的溢出
        long C = 1;
        for (int i = 0; i < n; ++i) {
            C = C * 2 * (2 * i + 1) / (i + 2);
        }
        return (int) C;
    }

}
